\section{Inkrementálne hašovanie}

Predstavme si, že máme dlhý dokument (súbor alebo disk),
označme ho $m$ a chceme si uchovávať jeho haš napríklad kvôli
integrite alebo autenticite. Pri klasickom riešení
by sme museli prejsť celý dokument a spočítať jeho 
haš $H(m)$. Následne keď urobíme čo i len najmenšiu
zmenu, tak na to, aby sme získali nový haš musíme opäť
prejsť celý súbor. Toto je náročné na systémové prostriedky
a veľmi neefektívne. Predstavíme si preto niekoľko riešení, ktoré sa
snažia riešiť tento problém a ukážeme ich nedostatky.

\subsection{Triviálne riešenia}

Môžeme náš dokument rozdeliť na časti (disk na sektory)
a uchovávať haš každej časti osobitne. V prípade, keď
$m = m_1 m_2 \dots m_k$, tak haš bude 
$H(m) = \langle h(m_1), h(m_2), \dots, h(m_k) \rangle$.
Toto riešenie má ale príliš dlhý výsledný haš.
Takisto, z pohľadu autenticity nie je nič moc, že vieme
preusporiadavať bloky.

Iné riešenie je použiť Merkleho stromy. Ale aby
sme mali rýchly update hašu musíme pamätať zloženie celého stromu,
čo tiež nie je potešujúce.


\subsection{Lepšie riešenia}

Zoberme konečnú komutatívnu grupu $(G, \odot)$ (napríklad $(2^n, \oplus)$).
Následne predpokladajme, že máme hašovaciu funkciu s oborom hodnôť $G$.
Rozdeľme dokument na $k$ blokov $m = m_1 m_2 \dots m_k$, každý
veľkosti $n$. Náš haš bude 
\begin{equation*}
    H(m) = \bigodot_{i=1}^k h(i, m_i)
\end{equation*}
Pokiaľ sa blok $m_i$ zmení na $m_i'$, tak nový haš vypočítame
nasledovne:
\begin{equation*}
    H(m') = H(m) \odot h(i, m_i)^{-1} \odot h(i, x_i')
\end{equation*}

\subsubsection{Súvislosť s problémom vyvažovania}

Dá sa ukázať, že nájsť kolíziu pre inkrementálnu hašovaciu
funkciu nad grupou $G$ je aspoň tak ťažké ako riešiť
problém vyvažovania (ktorého obťiažnosť závisí hlavne od grupy 
$G$). Vo všeobecných grupách sa verí, že tento problém je
NP-ťažký.\footnote{Pozor, nie NP-úplný.}

\begin{definicia}[Problém vyvažovania]
    Máme zadanú grupu $(G, \odot)$ a postupnosť $a_1, a_2, \dots, a_n$.
    Našou úlohou je nájsť čísla $w_1, w_2, \dots, w_n \in \{-1, 0, 1\}$,
    kde aspoň jedno z nich je nenulové a platí 
    $a_1^{w_1} \odot a_2^{w_2} \odot \dots \odot a_n^{w_n} = e$.
    Tomuto problému hovoríme problém vyvažovania.
\end{definicia}

\begin{poznamka}
    Pokiaľ je grupa $G$ komutatívna, tak vlastne hľadáme
    dve neprázdne disjuktné podmnožiny
    $I, J \subseteq \{1, 2, \dots, n\}$, kde platí 
    $\bigodot_{i\in I} a_i = \bigodot_{j \in J} a_j$.
\end{poznamka}

\begin{lema}
    Ak vieme v grupe $(G, \odot)$ hľadať kolízie pre inkrementálne hašovacie
    funkcie, tak vieme rovnako efektívne riešiť problém vyvažovania.
\end{lema}

\begin{dokaz}
    Majme program $A$, ktoré hľadá kolíziu pre inkrementálnu hašovaciu
    funkciu nad grupou $(G, \odot)$. Tento program nám položí $q$ otázok
    typu ``aká je hodnota $h(i, x_i)$?'' Na tieto otázky mu odpovieme postupne
    hodnotami $a_1, a_2, \dots, a_q$.
    Program následne vyprodukuje odpoveď $H(x) = H(y)$, čo je vlastne 
    $\bigodot_{i \in I} a_i = \bigodot_{j \in J} a_j$.
    (Keďže predpokladáme, že funkcia $h$ sa správa ako náhodné orákulum,
    tak sa na všetky zložky $x$ a $y$ musí $A$ opýtať.)
\end{dokaz}
\fixme{Tento dôkaz je pochybný -- problémy: 1. čo ak máme otázok viac,
 2. A čo randomizácia? Ak vieme hľadať kolízie iba pravdepodobnostne,
 tak tento postup nefunguje}

\subsection{XOR-HASH}

Najprv si ukážeme tzv. XOR-HASH.
Predpokladajme, že $h\colon \{0,1\}^n \to \{0,1\}^l$.
Haš bude daný vzorcom
\begin{equation*}
    H(m) = \bigoplus_{i=1}^k h(i, m_i)
\end{equation*}

Ukážeme, že aj v prípade, že aj v prípade ak $h$ je kvalitná hašovacia funkcia
(správa sa ako náhodné orákulum) vieme XOR-HASH invertovať.

Na vstupe majme hodnotu $z \in \{0,1\}^l$, ktorý chceme invertovať.
Najprv si pripravíme dva náhodné dokumenty (postupnosti blokov)
$m^{(0)} = m_1^{(0)} m_2^{(0)} \dots m_k^{(0)}$ a 
$m^{(1)} = m_1^{(1)} m_2^{(1)} \dots m_k^{(1)}$. Bolo by pritom
vhodné, aby zodpovedajúce si bloky boli rôzne, teda aby $\forall i:
m_i^{(0)} \ne m_i^{(1)}$.
Vypočítame si haše jednotlivých častí a označíme ich ako
$a_i^{(b)} = h(i, m_i^{(b)})$. 
Teraz chceme nájsť vektor $y = (y_1,y_2, \dots ,y_k)$, kde $y_i \in \{0,1\}$,
taký, aby platilo 
\begin{equation*}
    z = a_1^{(y_1)} \oplus a_2^{(y_2)} \oplus \dots \oplus a_k^{(y_k)}
\end{equation*}
(čo je inak povedané $H(m_1^{(y_1)} m_2^{(y_2)} \dots m_k^{(y_k)}) = z$).
Táto rovnica sa dá napísať aj ako:
\begin{equation*}
    z = a_1^{(0)} (1 - y_1) \oplus a_1^{(1)} y_1 \oplus \dots 
        \oplus a_k^{(0)} (1 - y_k) \oplus a_k^{(1)} y_k
\end{equation*}

Keďže $z$ má $l$ bitov a všetky tieto bity sa počítajú nezávisle od
ostatných, vieme zostaviť $l$ rovníc nad $Z_2$. 
A máme $k$ neznámych.
V praktických aplikáciách je $k > l$ 
a teda riešením sústavy dostaneme skoro vždy riešenie.

\todo{sanca na najdenie riesenia}

\subsection{Ad-hash}

Tento krát spravíme iteratívnu hašovaciu funkciu v grupe $(Z_u, +)$.
\begin{equation*}
    H(x) = \sum_{i=1}^k h(i, m_i) \pmod{u}
\end{equation*}
Tu sa dá ukázať, že problém vyvažovania pre $(Z_u, +)$ je ťažký. 
V praxi sa používajú napr. tieto 2 konštrukcie:

NASD konštrukcia:
\begin{equation*}
    H(x) = \sum_{i=1}^k h(i, m_i) \pmod{2^{256}}
\end{equation*}

DCIHF konštrukcia:
\begin{equation*}
    H(x) = \sum_{i=1}^{k-1} \textrm{SHA-1}(m_i, m_{i+1}) \pmod{2^{160}+1}
\end{equation*}

\subsection{Zovšeobecnený narodeninový útok}

Predstavme si, že máme dva zoznamy slov $L_1, L_2 \in \{0,1\}^n$ vygenerované
napríklad pomocou hašovacej funkcie. Teraz chceme nájsť
také $x_1 \in L_1, x_2 \in L_2$, že $x_1 = x_2$
resp. inak povedané $x_1 \oplus x_2 = 0$.

Toto je starý známy narodeninový útok. Pokiaľ obidva zoznamy budú mať veľkosť
$2^{n/2}$, tak máme celkom dobrú šancu, že takáto dvojica existuje. Nájdeme ju
už ľahko - jeden zoznam vložíme do hašovacej tabuľký a skúšame potom v tejto
tabuľke hľadať prvky z druhého zoznamu.
Celkový čas útoku by bol $O(2^{n/2})$.

Tento druh útoku môžeme zovšeobecniť pre $k$ zoznamov $L_1, L_2, \dots, L_k$.
Potom naša požiadavka na vybrané slová je: $x_1 \oplus x_2 \oplus \dots \oplus x_k = 0$.

Ukážeme si ako vieme jednoducho hľadať takéto slová pre $k=4$.

Vygenerujeme zoznamy $L_1, L_2, L_3, L_4$ s veľkosťou $2^{n/4}$. 
Následne vyrobíme všetky kombinácie $x_1 \oplus x_2$ a $x_3 \oplus x_4$, kde
$x_1 \in L_1, x_2 \in L_2, x_3 \in L_3, x_4 \in L_4$.
Každej z týchto kombinácií bude $2^{n/2}$. Následne prevedieme útok pre $k=2$.
Takže celkový čas opäť bude $O(2^{n/2})$.

Zatiaľ sme si ale veľmi nepomohli. Ale v roku 2002 Wagner \cite{birthday}
našiel rýchlejší útok.

Najprv si ale zadefinujme operáciu spojenia (join). Nech $low_l(x)$ predstavuje
posledných $l$ bitov slova $x$. Potom:
$L \bowtie_l L^{'} = \{(x, x^{'}) | x \in L \land x^{'} \in L^{'} \land low_{l}(x) = low_l(x^{'})\}$
Teda vyberieme z $L$ a $L^{'}$ tie dvojice slov, ktoré sa zhodujú na posledných
$l$ bitoch.

Teraz si ukážeme útok pre $4$ zoznamy. 
\begin{enumerate}
\item Pripravíme si zoznamy veľkosti $2^{n/3}$.
\item Vypočítame $L_{12} = L_1 \bowtie_{n/3} L_2$.
\item Vypočítame $L_{34} = L_3 \bowtie_{n/3} L_4$.
\item Vypočítame $L_{12} \bowtie L_{34}$.
\end{enumerate}

\begin{figure}
    \centering
    \includegraphics[scale=1]{img/07/birthday.1.mps}
    \caption{Zovšeobecnený narodeninový útok pre $k = 4$}
\end{figure}


Pozrime sa na časovú zložitosť. Očakávaná veľkosť $L_{12}$ bude $2^{n/3} \cdot 2^{n/3} / 2^{n/3} = 2^{n/3}$ (zoberieme všetky možné
dvojice a požadujeme rovnosť posledných $n/3$ bitov). V tomto istom čase vieme aj vygenerovať tento zoznam. To isté
dostaneme aj pre $L_{34}$. Očakávaná veľkosť výstupu z posledného kroku je $2^{n/3} \cdot 2^{n/3} / 2^{2n/3} = 1$.
Časová zložitosť opať bude $O(2^{n/3})$. Takto sme dosiahli oveľa lepšiu časovú zložitosť ako pôvodne.

Tento postup vieme zovšeobecniť pre ľubovoľné $k = 2^l$. 
Najprv si pripravíme zoznamy veľkosti $2^{\frac{n}{l+1}}$. Následne ich postupne spájame v strome, pričom
vo výške $v$ (výška úplne dole je $1$, smerom nahor rastie) spravíme join na posledných $w_v = \frac{vn}{l + 1}$
bitoch. Výnimka je koreň tam robíme join na všetkých $n$ bitoch.

\paragraph{Časová zložitosť:}
Každý nekoreňový join vyrobí $2^{\frac{n}{l+1}}$ dvojíc 
a trvá mu to čas $O(2^{\frac{n}{l+1}})$.
Koreňový join vyrobí jednu dvojicu a trvá mu to tiež čas 
$O(2^{\frac{n}{l+1}})$. Celkovo musíme urobiť $k-1$ joinov, takže
celková časová zložitosť je $O(k\cdot 2^{\frac{n}{1+lg k}})$.

\begin{figure}
    \centering
    \includegraphics[scale=1]{img/07/birthday.2.mps}
    \caption{Zovšeobecnený narodeninový útok pre $k=8$}
\end{figure}

Zatiaľ tento útok generuje iba $k$-tice pre ktoré platí: $x_1 \oplus x_2 \oplus \dots \oplus x_k = 0$. 
Ak chceme dosiahnúť rovnosť $x_1 \oplus x_2 \oplus \dots \oplus x_k = c$, stačí zmeniť $L_k$ na $L_k^{'}$
nasledovne: $L_k^{'} = \{x_k \oplus c | x_k \in L_k\}$. Potom keď nájdeme $x_1 \oplus x_2 \oplus \dots \oplus x_k^{'} = 0$,
tak $x_k^{'}$ zameníme za príslušné $x_k$ a máme splnenú podmienku, ktorú sme chceli.

Zároveň toto ukazuje, že pokiaľ chceme hľadať kolíziu pre nejaké $k^{'} > k$, tak to vieme
určite tak rýchlo ako pre $k$. Vyberme si nejaké $x_{k+1}, x_{k+2}, \dots, x_{k^{'}}$ a položme
$c = x_{k+1} \oplus x_{k+2} \oplus \dots \oplus x_{k^{'}}$. A potom nájdeme kolíziu pre prvých $k$ zoznamov. 

Takto by sme vedeli útočiť napríklad už na XOR-HASH. Vygenerujeme zoznamy a nájdeme kolíziu, ktorá nám po
vyxorovaní dá požadovanú hašovaciu hodnotu. Pre XOR to ale žiadny pokrok nie je, keďže vieme robiť
útok s ďaleko lepšou zložitosťou.

Útok sa dá uplatniť aj na Ad-Hash.
Pri grupe $(Z_{2^n}, +)$ bude join vyzerať nasledovne: $L_1 \bowtie_l L_2 = \{(x_1, x_2) | x_1 \in L_1 \land x_2 \in L_2 \land low_l(x_1 + x_2) = 0\}$.

Takto vieme zaútočiť na NASD schému. Napríklad pokiaľ by schéma mal 128 blokov, tak by čas útoku bol: $128 \cdot 2^{256/8} = 2^{39}$.

Pre grupu $(Z_m, +)$ použijeme nasledovný join: $L_1 \bowtie_{[a,b]} L_2 = \{(x_1, x_2) | x_1 \in L_1 \land x_2 \in L_2 \land x_1 + x_2 \in <a,b>\}$.


Pokiaľ chceme útočiť na PCIHF schému, tak najprv si zvolíme napevno hodnoty $x_2, x_4, x_6, \dots$ a následne dopočítame vhodné hodnoty medzi nimi.

